import java.util.*;
public class FindSquare {
    public int[] findSquare(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        
        int n = matrix.length;
        // right[i][j]: 从(i,j)向右连续0的数量
        int[][] right = new int[n][n];
        // down[i][j]: 从(i,j)向下连续0的数量
        int[][] down = new int[n][n];
        
        // 预处理right数组
        for (int i = 0; i < n; i++) {
            right[i][n - 1] = matrix[i][n - 1] == 0 ? 1 : 0;
            for (int j = n - 2; j >= 0; j--) {
                right[i][j] = matrix[i][j] == 0 ? right[i][j + 1] + 1 : 0;
            }
        }
        
        // 预处理down数组
        for (int j = 0; j < n; j++) {
            down[n - 1][j] = matrix[n - 1][j] == 0 ? 1 : 0;
            for (int i = n - 2; i >= 0; i--) {
                down[i][j] = matrix[i][j] == 0 ? down[i + 1][j] + 1 : 0;
            }
        }
        
        // 从最大的可能大小开始枚举
        for (int size = n; size >= 1; size--) {
            // 枚举所有可能的左上角位置
            for (int i = 0; i <= n - size; i++) {
                for (int j = 0; j <= n - size; j++) {
                    // 检查四条边是否都是黑色
                    // 上边：(i,j)向右至少size个0
                    // 左边：(i,j)向下至少size个0
                    // 右边：(i,j+size-1)向下至少size个0
                    // 下边：(i+size-1,j)向右至少size个0
                    if (right[i][j] >= size && 
                        down[i][j] >= size && 
                        down[i][j + size - 1] >= size && 
                        right[i + size - 1][j] >= size) {
                        return new int[]{i, j, size};
                    }
                }
            }
        }
        
        return new int[0]; // 没有找到满足条件的方阵
    }

    public static void main(String[] args) {
        // 测试用例1
        int[][] matrix1 = {{1,0,1},{0,0,1},{0,0,1}};
        FindSquare fs = new FindSquare();
        int[] result1 = fs.findSquare(matrix1);
        System.out.println(Arrays.toString(result1));
        
        // 测试用例2
        int[][] matrix2 = {{0,1,1},{1,0,1},{1,1,0}};
        int[] result2 = fs.findSquare(matrix2);
        System.out.println(Arrays.toString(result2));
        
        // 用户提供的测试用例
        int[][] matrix3 = {
            {1, 1, 1, 1, 0, 1, 0, 1, 1, 1},
            {1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
            {1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
            {1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
            {1, 0, 1, 0, 1, 1, 1, 1, 1, 1},
            {1, 1, 0, 0, 1, 0, 1, 0, 0, 1},
            {0, 0, 0, 1, 1, 1, 0, 1, 0, 1},
            {0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 1, 0, 1, 1, 1},
            {1, 1, 1, 0, 1, 0, 0, 1, 1, 1}
        };
        int[] result3 = fs.findSquare(matrix3);
        System.out.println(Arrays.toString(result3)); // 应该输出[1,4,3]
    }
}

//，题目要求找出 4条边皆为黑色像素的最大子方阵 ，而不是全为黑色的方阵。当前的实现是寻找全为0的方阵
// ### 正确的实现思路
// 要找出四条边都是黑色(0)的最大子方阵，我们需要：

// 1. 1.
//    预处理矩阵，计算每个位置向右和向下连续0的数量
// 2. 2.
//    枚举可能的方阵大小，从大到小
// 3. 3.
//    对于每个可能的大小，检查所有可能的左上角位置
// 4. 4.
//    验证该位置的四条边是否都是黑色